package code.notdo;

/**
 * author： yeswater
 * create： 2023/12/22
 *
 * 戳气球 hard
 *
 */
public class T312 {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] copyNums = new int[n+2];
        copyNums[0] = copyNums[n+1] = 1;
        int[][] dp = new int[n+2][n+2];
        
        for(int i=0; i<n; i++){
            copyNums[i+1] = nums[i];
        }
        
        for(int len=2; len<n+2; len++){
            for(int left=0; left+len<n+2; left++){
                int r = left + len;
                int ij = copyNums[left]*copyNums[r];
                int tempDp = 0;
                for(int k=left+1; k<r; k++){
                    tempDp = Math.max(tempDp, dp[left][k]+dp[k][r]+copyNums[k]*ij);
                }
                dp[left][r] = tempDp;
            }
        }
        return dp[0][n+1];
    }
}
